This tag is for basic questions about the study of finite or countable discrete structures — specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions. ...

learn more… | top users | synonyms (4)

1
vote
1answer
247 views

The number of symmetric polynomials of n degree

How many symmetric polynomials of n degree with all their coefficients $\ =1 $ are there?Is there a type that computes their number?
2
votes
1answer
515 views

Given an alphabet with 26 letters, how many reduced alphabets are possible?

Please help me count. I have an alphabet with 26 English letters. I can reduce it to 25 letters by representing two of the letters (e.g. O and X) with a new letter (e.g. $\otimes$). 25 To get down ...
1
vote
1answer
220 views

Representability as a Sum of Three Positive Squares or Non-negative Triangular Numbers

Let $r_{2,3}(n)$ and $r_{t,3}(n)$ denote the number of ways to write $n$ as a sum of three positive squares (A063691) and as a sum of three non-negative triangular numbers (A008443), respectively. I ...
2
votes
3answers
167 views

Number of combinations w/o repetition that include a certain element

Given the number of combinations w/o repetition for a set of size n from which you choose k is given by: n! / k! * (n - k)! How does one calculate the number of these combinations that include a ...
8
votes
1answer
328 views

How many strings of length $n$ with $m$ $1$s have no more than $k$ consecutive $1$s? - from generatingfunctionology

Here is a problem from generatingfunctionology that I'm stuck on: I'm trying to get started on part (a). I broke the string up like this. If the last digit is $0$, the number of possible strings is ...
6
votes
0answers
117 views

Generalizing Quadratic Reciprocity Law with Dilates

Eisenstein's proof of the Quadratic Reciprocity (QR) (and its Jacobi symbol generalization) both rely on counting lattice points in two congruent triangles. If we take $t$-dilates of these triangles, ...
0
votes
1answer
51 views

Applications of the Formal Laurent Lattice

Attach a (Laurent) monomial weight $x_1^{i_1} \cdots x_n^{i_n}$ to each point $(i_1, \dots, i_n)$ of $\mathbb{Z}^{n}$ and call it $\mathbb{Z}^{n}[x_1, x_{1}^{-1}, \dots, x_n, x_n^{-1}]$. Does this ...
4
votes
2answers
1k views

the number of Young tableaux in general

From the wiki page Catalan number, we know the number of Young tableaux whose diagram is a 2-by-n rectangle given $2n$ distinct numbers is $C_n$. In general, given $m\times n$ distinct numbers, how ...
5
votes
1answer
979 views

Counting paths in a square matrix

Question: Consider a square matrix of order $m$. At each step you can move one step to the right or one step to the top. How many possibilities are to reach $(m,m)$ from $(0,0)$? I think ...
4
votes
1answer
448 views

Permutation Inversion Questions (3)

Working my way through a combinatorics text and I'm hung up on a couple of questions: 1.) Let $p=p_1 p_2\cdots p_n$ be a permutation. An inversion of $p$ is a pair of entries $(p_i,p_j)$ so that ...
5
votes
2answers
73 views

Formula for $\binom{n}{2}/\binom{m}{2}=1/2$ or $2n(n-1) = m(m-1)$?

Where could I find a formula that produces integers $n$ and $m$ such that $\binom{n}{2}/\binom{m}{2}=1/2$? Of course, this questions can be reformulated as: How to find all the integer values of n ...
19
votes
2answers
2k views

Expected number of rolling a pair of dice to generate all possible sums

A pair of dice is rolled repeatedly until each outcome (2 through 12) has occurred at least once. What is the expected number of rolls necessary for this to occur? Notes: This is not very deep ...
4
votes
2answers
314 views

Natural set to express any natural number as sum of two in the set

Any natural number can be expressed as the sum of three triangular numbers, or as four square numbers. The natural analog for expressing numbers as the sum of two others would apparently be the sum ...
15
votes
6answers
2k views

Why are generating functions useful?

I was under the mistaken impression that if one could find the generating function for a sequence of numbers, you could just plug in a natural number $n$ to find the nth term of the sequence. I ...
1
vote
1answer
141 views

Sequences and Finite Differences

Given the sequence $\{ f(i) \}_{0 \leq i \leq n}$ and the array $\{ g_{n}(i,j) \}_{0 \leq i, j \leq n}$ such that $f(i) = \sum_{j = 0}^{n} h_{j} \, g_{n}(i,j)$ for some integers $h_{0}, \dots, h_{n}$, ...
6
votes
1answer
230 views

What is the number of ways to choose x groups from y items? (partitions with x cells of a multiset)

Where a group can consist of 1 or more items, groups don't have to be equally sized and items can be duplicates. Example - Choose 3 groups: Items: 1 2 2 3 Groups: (1) (2 2) (3) (1 2) (2) (3) (3 ...
31
votes
3answers
475 views

Guessing a subset of $\{1,…,N\}$

I pick a random subset $S$ of $\{1,\ldots,N\}$, and you have to guess what it is. After each guess $G$, I tell you the number of elements in $G \cap S$. How many guesses do you need?
1
vote
1answer
110 views

are there useful bounds on the “gamma” coeficients (generalization of multinomial coefficients)?

Let $a_1,\ldots,a_n$ be a set of $n$ positive numbers. Are there known lower and upper bounds on: $\displaystyle\frac{\prod_{i} \Gamma(a_i)}{\Gamma(\sum_i a_i)}$ where $\Gamma$ is the Gamma ...
10
votes
4answers
2k views

Looking to understand the rationale for money denomination

Money is typically denominated in a way that allows for a greedy algorithm when computing a given amount $s$ as a sum of denominations $d_i$ of coins or bills: $$ s = \sum_{i=1}^k n_i ...
5
votes
1answer
125 views

Database of binary linear codes (including bad ones)

I am looking for all $k$-dimensional subspaces of $(\mathbb{Z}/2\mathbb{Z})^n$ up to permutational equivalence. Is there a database of all $[n,k]$-codes up to equivalence for reasonable values of ...
7
votes
2answers
307 views

A binomial coefficient identity?

Suppose $p$, $k$ and $s$ are integers with $s,k \le p$. Consider the following polynomial in $x$ and $y$, $$ \sum_{\ell=0}^k \binom{s}{\ell} \binom{p-s}{k-\ell} x^\ell y^{p-\ell}$$ Does this ...
5
votes
4answers
343 views

How to prove the equality $\sum_{j=0}^n (x)^j (-1)^{n-j} \left\{{n \atop j}\right\} = x^n$?

How do you prove $$\sum_{j=0}^n (x)^j (-1)^{n-j} \left\{{n \atop j}\right\} = x^n,$$ where $(x)^j=x(x+1)...x(x+j-1)$ and $\left\{{n \atop j}\right\}$ is a Stirling number of the second kind?
2
votes
3answers
166 views

How can I prove the formula for calculating successive entries in a given row of Pascal's triangle?

I've found in Wikipedia the formula for calculating an individual row in Pascal's Triangle: $$v_c = v_{c-1}\left(\frac{r-c}{c}\right).$$ where $r = \mathrm{row}+1$, $c$ is the column starting from $0$ ...
4
votes
1answer
592 views

Using generating functions to find a formula for the Tower of Hanoi numbers

So the Tower of Hanoi numbers are given by the recurrence $h_n=2h_{n-1}+1$ and $h_1=1$. I let my generating function be $$ g(x)=\sum h_nx^n $$ Then $$ g(x)=\sum h_n x^n=\sum (2h_{n-1}+1)x^n=\sum ...
3
votes
2answers
271 views

Why does $\mu(k,n)=\mu(1,\frac{n}{k})$?

Why does $\mu(k,n)=\mu(1,\frac{n}{k})$, where $\mu$ is the Möbius function and $k$ and $n$ are integers. I'm reading about the Möbius function on a poset of integers ordered by divisibility. The ...
6
votes
5answers
251 views

Identity for $\sum\limits_{j = a}^{N} \binom{N}{j} \binom{j}{a} d^{-j}$?

I have run across the following multinomial series: $$ \sum_{j = a}^{N} \binom{N}{j} \binom{j}{a} d^{-j} $$ Here, $d>1$. This seems like a formula which has either a well-known identity, ...
10
votes
1answer
454 views

Random points in a rectangular grid defining a closed path

Suppose we have a $n\times m$ rectangular grid (namely: $nm$ points disposed as a matrix with $n$ rows and $m$ columns). We randomly pick $h$ different points in the grid, where every point is ...
7
votes
1answer
100 views

Upper bound of the number of local swaps

Let $\pi$ be an arbitrary permutation of the set $\lbrace 1,\ldots,n,n+1,\ldots,2n \rbrace$ for some $n \in \mathbb{N}$. We call a swap local if you swap two neighboring positions in $\pi$, i.e. if ...
7
votes
1answer
121 views

Has this Extension to a Series been Studied Before?

We know from Calculus what a series is, and you might have seen infinite products as well. But the Elementary Symmetric Polynomials give an entire spectrum of operators between a sum and product over ...
2
votes
2answers
91 views

Need a nudge in the right direction - How do I find the total number of permutation with 3 consecutive characters?

Again, I really just want a nudge in the right direction. Possibly a large nudge, but not the straight forward answer. I am trying to figure out how to solve Project Euler Problem 191. I believe I ...
1
vote
1answer
144 views

Yet another permutation problem

There is a square table and 2 persons are sitting on each side of it so there are 8 persons in total ... how many total number of permutation is possible? Does circular permutation rules applies ...
0
votes
2answers
187 views

Choose 4 types of soup from 10 varieties, with constraint?

We have to choose 4 types of soup from a supermarket's 10 varieties, such that at least 2 are identical. In how many ways can we do this ? We have 10 varieties of soup like so {v1, .. v10}. We can ...
1
vote
1answer
439 views

Is this identity involving Stirling numbers of the first kind well-known?

I've been looking in vain (most books I came across give identities involving sums or recurrence relations, but do not give much attention to fixed values) for a reference to the following identity: ...
2
votes
3answers
1k views

Maximum number of triangles formed by points on a square?

$N$ points are to be put on sides of a square. What's the maximum number of triangles which are formed by joining those points? Hints would be appreciated.
4
votes
1answer
206 views

what is a tight lower bound on the coupon collector time?

In the classic Coupon Collector's problem, it is well known that the time $T$ necessary to complete a set of $n$ randomly-picked coupons satisfies $E[T] \sim n \ln n $,$Var(T) \sim n^2$, and $\Pr(T ...
0
votes
1answer
166 views

an arrangement of 10 objects, with restriction

We have 10 bricks, 3 red, 2 white, 2 yellow, 2 blue, 1 black. In how many ways can these be arranged such that only 2 red bricks are adjacent ? We want to distribute the elements in {RR, R} over the ...
1
vote
3answers
279 views

Fibonacci Numbers: Is This Notation Clear? How Can It Be Improved?

I am writing up an assignment with includes many identities of Fibonacci numbers. I have made up the following notation (here $f_n$ is the number of tilings of an $n$-board by dominoes and squares - a ...
13
votes
1answer
638 views

Rubik's cube interesting questions?

The upper bound for the number of moves required to solve a regular Rubik's cube has been shown to be 20. Two questions come to mind: Does this result have more general significance? What are the ...
0
votes
1answer
144 views

How many ways to pair wine and food? [closed]

I have the following homework, for which I'd like you to give me some hints. Thank you. There are M food dishes and N bottles of different wines. There are 4 ways to pair food and wine: 1 (dish) to 1 ...
2
votes
1answer
213 views

How many perms of 4 from letters of MATHEMATICS?

The answer is 2454, apparently. I am getting 1446, however. Can anyone point out my error ? We need to partition the solution into the mutually exclusive cases of choices of 4 letters where we have ...
11
votes
2answers
260 views

What is the probability that $\pi(x) + x$ is injective?

Let $S$ be a finite group with operator + and $\pi$ be a permutation on $S$. Then what is the probability that $\pi(x) + x$ is injective over choices of $\pi$? The concrete instantiation I'm ...
8
votes
0answers
157 views

Reconstruction Conjecture and Partial 2-trees

Reconstruction conjecture says that graphs (with at least three vertices) are determined uniquely by their vertex deleted subgraphs. This conjecture is five decades old. Searching relevant ...
7
votes
1answer
232 views

On the existence of closed form solutions to finite combinatorial problems

Is it possible that a finite combinatorial problem may admit a closed form solution, and for it to be impossible in practice to prove the validity of this solution? I'm not sure if a rigorous ...
2
votes
2answers
460 views

Number of ways to get exactly one 3 of a kind from 9 dice

This question stems from Probability of 3 of a kind with 7 dice as a means to check my understanding. I'm not sure whether this is general practice on this website, so I'm sorry if creating a new ...
5
votes
1answer
654 views

Upper bound on summation involving binomial coefficients

I am trying to upper bound the following sum: $$\sum_{k=1}^{n/2} \frac{\binom{n-2}{k-1}k^{k-2}(n-k)^{n-k-2}}{n^{n-3}}.$$ Based on numerical computations, it seems like the upper bound is a constant ...
3
votes
1answer
214 views

Recurrence representation(s): $a(n+1)=a(n)(n-1/2)+o(1/n)$ and $a(n+1)=a(n)(n-1/2+o(1/n))$

I know that the recurrence $\displaystyle a(n+1)=a(n)(n-1/2)$ can be represented like $\displaystyle \frac{(2n-1)!!}{2^n}$ Actually the initial recurrence is slightly different: $$\displaystyle ...
1
vote
1answer
651 views

Upper bound on integer partitions of n into k parts

Recent news piqued my interest in integer partitions again. I'm working my way back through an old text and I'm completely hung up on this problem: Recall that $p_k(n)$ is the number of partitions ...
6
votes
1answer
84 views

How to prove that if $\#A = n$, then $\#A^{k} = n^{k}$? And what about the formula $\frac{n!}{(n-k)!}$?

I'm starting a mini-course on Combinatorics and, although I can "see" the results, I'm having difficulties proving them. For instance, Being $\#A = n \in \mathbb{N}$, prove that $\#A^{k} = ...
4
votes
2answers
456 views

Poker combinations & probability

I'm trying to figure out how I can work out the number of possible valid hand combinations of a poker game that a player (opponent) could possibly have when the flop has been dealt on the table. So ...
6
votes
2answers
258 views

The ratio in terms of sets

The recurrence $a_{n+1}=a_n(n-1/2)$ is related to $\Gamma(n+1/2)$ ( not difficult to prove) and it could be represented in a way like $\frac {(2n-1)!!} {2^n}$ Also I know that $(2n-1)!!$ is the ...