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
28 views

Number [n,k]-linear codes with one fixed vector

I need to find the number of $[n,k]$-linear binary codes with one fixed codeword x (non zero) in it. So I guess, I need to count the number of $k$-dimensional ...
5
votes
3answers
65 views

How many sequences of numbers $\{a_1…a_5\}$ where $a_i \in \{1…25\}$ satisfy $a_{i+1} \leq a_i + 2$

Here's how it looks: 1 1 1 1 1 1 1 1 1 2 1 1 1 1 3 1 1 1 2 1 1 1 1 2 2 1 1 1 2 3 1 1 1 2 4 1 1 1 3 1 ......... 25 25 25 25 24 25 25 25 25 25 Counting sequences ...
1
vote
1answer
47 views

How many random cards picks with replacement are required?

You pick 1 card from a standard deck of 52 cards. Then put it back in, and pick a card again. Then put it back in and pick a card. etc... How many times do you have to repeat in order to have ...
1
vote
2answers
25 views

$K$ events that are $(K-1)$-wise Independent but not Mutually/Fully Independent

I had the following question: Construct a probability space $(\Omega,P)$ and $k$ events, each with probability $\frac12$, that are $(k-1)$-wise, but not fully independent. Make the sample space as ...
0
votes
0answers
57 views

Proportional growing number set $\mathbb{X}\subset\mathbb{N}$

1. Question: Is there such a set of numbers $\mathbb{X}\subset\mathbb{N}$, in which the proportion of product and sum of all natural numbers $n\in \mathbb{N}$ grow proportional? $$\begin{equation*} ...
0
votes
0answers
19 views

finding the least non-zero of a multivariable polynomial

Let $P(x_1,x_2,...,x_m)$ be a homogeneous polynomial of degree n, with integers coefficients. How can you find the least* $a=(a_1,a_2,...,a_m)$, where $a_i$ are positive integers and $P(a)!\neq 0$? ...
1
vote
0answers
13 views

Generalized permutahedron and random polytopes

The Birkhoff polytope $B_n$ is defined as the convex hull of the set of permutation matrices, which gives us the set of doubly stochastic matrices. A concept which is intimately related is that of the ...
1
vote
1answer
26 views

Partitioning N people into N/2 sized groups across N - 1 days

Problem Statement: Given a list of $N$ people. On the 1st day, divide them into $N/2$ groups of two people each. On the 2nd day, divide them into groups of two again... Do this every day, until day ...
0
votes
1answer
54 views

Number of seating arrangements in 5 cars

An exercise from Introductory Combinatorics by Richard A.Brualdi: A roller coaster has five cars, each containing four seats, two in front and two in back. There are 20 people ready for a ride. ...
1
vote
0answers
55 views

Number of paths in a grid

A common puzzle problem is to count the number of paths that start from the bottom-left-hand corner of a grid and end at the top-right hand corner, with the restriction that you can only move upwards ...
5
votes
1answer
212 views

Is there a name for this problem I can search for approaches on

I have a collection of a collection of numbers that I need to find the smallest number of groups to put them into whereas the distinct set of numbers in each set does not exceed a threshold. For ...
0
votes
1answer
14 views

number of elements in unsortet case

I have a group M with Mn different elements. How many unique combinations can I make out of this in an n digit system when order is no importance. For example if M = {1 2} & n = 3 ...
1
vote
0answers
34 views

Confusion related to k neighborly polytope

I was reading this paper related to neighborly polytope where they mentioned: Consider a $d \times n$ matrix $A$, with $d < n$. The problem of solving for $x$ in $y = Ax$ is underdetermined, ...
3
votes
3answers
406 views

Probability of having at least $K$ consecutive zeros in a sequence of $0$s and $1$s

I have a sequence of length $N$ consisting of $M$ ones and $N-M$ zeros. I am trying to find the number of possible arrangements that produce a sequence in which there exist at least K consecutive ...
4
votes
0answers
88 views

Multiplicative subgroup of a finite field with prescribed trace.

Any suggestions/methods/estimates for the following problem would be very appreciated. $l,p$ are primes with $p \equiv 1 \!\! \pmod l$. $r$ is a positive integer with $r \equiv 1 \!\! \pmod p$ and $q ...
0
votes
0answers
25 views

Combinatorics of relations

Let A = {1,2,3}. Find the total number of relations on A that are both symmetric and transitive. I know that there are 64 symmetric relations, but how can I find out of those how many are transitive ...
1
vote
1answer
58 views

How many zeros does this expression end in?

How many zeroes does $$\frac{50!}{2^95^5}$$ end in?
41
votes
6answers
12k views

Probability that random moves in the game 2048 will win

I have recently played the game 2048, created by Gabriele Cirulli, which is fun. I suggest trying if you have not. But my brother posed this question to me about the game: If he were to write a ...
0
votes
2answers
25 views

Visualizing generalized basic principle of counting

The basic principle of counting states: Suppose that two experiments are to be performed. Then if experiment 1 can result in any one of m possible outcomes and if, for each outcome of experiment ...
0
votes
1answer
36 views

Round Robin for Team Matches

My question came from the Bridge-game (Teams). This is what happens: Ideally, there are 4 pairs (A,B,C,D). We have 2 tables. In every table, there are 2 pairs. One pair is sitting in the North-South ...
3
votes
2answers
104 views

Counting Shaded Squares

In a $4 \times 4$ square, how many different patterns can be made by shading exactly two of the sixteen squares? Patterns that can be matched by flips and/or turns are not considered different. How ...
1
vote
3answers
43 views

P white balls, Q black balls, N boxes

First of all sorry if this has been asked before, I could find "similiar" questions which seem to be harder but not quite this specific question. You are given P white balls and Q black balls, how ...
0
votes
1answer
19 views

How many functions defined on $n$ points are possible if each functional value is either $0$ or $1$?

How many functions defined on $n$ points are possible if each functional value is either $0$ or $1$? This is from the text A First Course on Probability by Sheldon Ross. The solution he ...
0
votes
0answers
19 views

Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
3
votes
2answers
57 views

Counting divisibility from 1 to 1000

Of the integers $1, 2, 3, ..., 1000$, how many are not divisible by $3$, $5$, or $7$? The way I went about this was $$\text{floor}(1000/3) + \text{floor}(1000/5) + ...
0
votes
0answers
15 views

Counting all possible tournament results with variable subsets removed [closed]

Given a 16 person, 4 round, single elimination tournament where the initial draw is known, what is a formula to determine the number of possible combinations if some subset(s) is removed? For example, ...
0
votes
2answers
36 views

Different values of $x$ and $y$ between $\sqrt{39}$ and $\sqrt{224}$

If $x$ and $y$ are whole numbers between $\sqrt{39}$ and $\sqrt{224}$, then how many different values can $x$ + $y$ have? OK, first I found that the set numbers are: $$7, 8 ,9 ,10 ,11 ,12, 13,14$$ ...
1
vote
1answer
20 views

Combinatorial interpretation of identity for stirling number of second kind

I'm trying to find a combinatorial interpretation for the following identity $$S(n+1, m+1)=\sum_{k=m}^{n}\binom{n}{k}S(k,m)$$. And am having a lot of trouble thinking of one. Any pointers?
0
votes
1answer
22 views

what is the number of possibilities

I have 9 variables that can vary each from 0 to 100.(natural number). And the sum of the first 3 should be between 20 and 30. And the sum of the 9 variables should be equal to 100. What is the number ...
1
vote
1answer
212 views

Permutation & Combination - how many numbers smaller than $2.10^8$ and are divisible by $3$ can be written by means of the digits $0$,$1$ and $2$

How many numbers smaller than $2.10^8$ and divisible by $3$ can be written by means of the digits $0$,$1$ and $2$? Left Zero padding not allowed. I am getting this as - 3 digits - 2*3 = 6 4 digits - ...
0
votes
4answers
31 views

Finding nth term application problem

I was given this question class today and I wasn't quite sure how to solve it "There are $10$ computers all connected with a cable to each other computer" 1) How many wires are there? 2) How many ...
4
votes
2answers
93 views

Green balls and Red balls, probability problem

I'm studying for my exam and I came across the following draw without replacement problem : ...
1
vote
2answers
31 views

The binomial formula. how to show: $\Sigma_{k=0}^n k \binom{n}{k} = n2^{n-1}$ [duplicate]

Does anyone know how to show that: $\Sigma_{k=0}^n k \binom{n}{k} = n2^{n-1}$? I think we are suppose to use the binomial formula for that.. Thank you!
2
votes
2answers
25 views

number of options to divide $n$ white balls into $r$ cells

I am trying to solve the following question: number of options to divide $n$ white balls into $r$ cells. or, more specifically: what is the number of options to divide 4 white balls into 3 cells? ...
2
votes
1answer
51 views

Seating $2n$ people around a table with each person has at most $n-1$ friends

I am trying to show that with the setting in the title, that it is always possible to arrange the seats so that no person sits beside his/her friend. I am not good at this kinds of problems at all, ...
0
votes
1answer
18 views

Sperners lemma how to mark internal vertices

Was reading sperners lemma from this http://www.math.hmc.edu/funfacts/ffiles/20001.4.shtml Couldn't understand certain things How to mark internal vertices? I could have mark some other number for ...
4
votes
1answer
52 views

How many surjective functions are there from $A=${$1,2,3,4,5$} to $B=${$1,2,3$}?

I want to find how many surjective functions there are from the set $A=${$1,2,3,4,5$} to the set $B=${$1,2,3$}? I think the best option is to count all the functions ($3^5$) and then to subtract the ...
1
vote
2answers
63 views

If you're playing darts and your probability of hitting the bullseye is 1/3, what's the probability you'll hit it with less than 10 shots? [closed]

If random variable X = number of shots till the first bullseye then X ~ Geo(1/3) With this how would I solve P(X<10)? Also, what if you want to find the probability of 3 hits in less than 10 ...
1
vote
2answers
170 views

Number of ways to form a 3-letter word with repetition allowed?

The additional rule is: no letter can be used more often than it appears in MILLENNIUM? (Which is pretty logical I guess) MILLENNIUM = MM, II, LL, NN, E, U My logic: Case 1: Double letters + 1 ...
0
votes
3answers
72 views

Forming words from letters

If we have five letters e.g. a,b,c,d,e a. How many four-letter words can we make that have exactly two vowels and two consonants? b. from (a), how many of those words have distinct vowels?
0
votes
2answers
142 views

No. of 5-digit monotonic numbers

The monotonic number is made of digits 1, 2, …, 9, such that each subsequent number equal to or greater than the previous number. Examples: 11119, 12369, 18999 etc. I understand that I can isolate ...
0
votes
3answers
52 views

Are the following sets countable?

I'm trying to determine if the following sets are countable: (a) $\mathbb{Z}^{[0,1]}, (b) [0,1]^{\mathbb{Z}}, (c) \mathbb{Z}^{\mathbb{Z}}$, (d) the set given by functions $f:\mathbb{Z}\to\mathbb{R}$ ...
0
votes
2answers
35 views

Solving Problem by different Method ( non-induction)

I have this problem , which I was able to prove it by induction, but I wonder could be solve by direct method ( for example combinatorial method). I want to find number of solution for $$0 \le ...
1
vote
0answers
28 views

Proof of the Catalan number formula using Dyck walks

In our notes we were given the formula $C(n)=\frac{1}{n+1}\binom{2n}{n}$ It was proved by counting the number of paths above the line y=0 from (0,0) to (2n,0) using n(1,1) up arrows and n(1,-1) down ...
2
votes
5answers
185 views

Deriving Closed Form for a Recursion via Generating Functions

Consider (1) $a_{n+2} = 2a_{n+1} - a_n + 4n3^n$ with $a_0 = a_1 = 1$. Using generating functions and setting $A(x) = \sum a_nx^n$ we obtain $$\begin{align*}&\quad\sum a_{n+2}x^{n+2} = ...
1
vote
0answers
34 views

How to answer the following question related to counting the number of trees of a graph?

I am asked to prove the equality $$ 2(n-1)n^{n-2} = \sum_{k=1}^{n-1} \binom{n}{k} k(n-k)T(k)T(n-k) , $$ where $T(k)$ is the number of different trees with $k$ numbered vertices. I think the ...
2
votes
3answers
117 views

Functional equations and generating functions

The problem asks to find the functional equations for the generating functions whose coefficients satisfy $$ a_n = \sum_{i=0}^{n-1} a_i a_{n-1-i}\,\, (n\geq1), a_0 = 1 $$ There's an example that's ...
1
vote
2answers
46 views

Coefficients of this generating function

For the first part of a problem, I solved the generating function to be $F(x) = \frac{x^3}{(1-x)^2}$ Now it's the easy part that has me a little confused. What would the coefficients be in this case? ...
2
votes
3answers
79 views

Solving recurrence relation with generating functions - Nearly got the answer

I'm trying to solve the following recurrence relation (Find closed formula) using generating functions: $f(n)=10f(n-1)-25f(n-2)$, $f(0)=0$, $f(1)=1$ I'm having a small difficulty at the end and can ...
0
votes
2answers
29 views

Counting integer solutions

how many integer solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 24$ where $x_1 \ge 0, x_2 \ge 1, x_3 \ge 2, x_4 \ge 3$ I have no idea how to go about this problem. Any help would be ...